package sort;


/**
 * 归并排序
 */
public class MergeSort {

    public static void main(String args[]){
        //输入
        int[] a=new int[]{3,20,9,1,6,2,12,231,2,5545,66,7,1,23,4,1};
        //打印
        printIntArray(a);
        System.out.println("\n==============");
        //merge(a,0,a.length/2,a.length);
        //归并排序开始
        startSort(a);
        //打印
        printIntArray(a);
    }

    public static  void startSort(int a[]){
        //开始递归
        mergeSort(a,0,a.length-1);
    }

    public static void mergeSort(int[] a,int begin,int end){
        //取首尾下标的中间下标 向下取整
        int p =(begin+end)/2;
        if( begin < end ){
            mergeSort(a,begin,p);
            mergeSort(a,p+1,end);
            merge(a,begin,p,end);
        }
    }

    public static int[]  merge(int[] a,int begin,int point,int end){
        int length=end-begin;
        //如果长度首尾下标差为1 则单独判断 比较大小 并按排序交换
        if(length==1){
            if(a[begin]>a[end]){
                int temp=a[begin];
                a[begin]=a[end];
                a[end]=temp;
            }
            return a;
        }
        //加1是 begin下标自身整数的长度也算进去
        int length_c = point - begin + 1;
        int length_d = end - point;

        //  int b[]=new int[length];

        int c[]=new int[length_c];
        for(int i=0;i<length_c;i++){
            c[i]=a[begin+i];
        }
        int d[]=new int[length_d];
        for(int i=0;i<length_d;i++){
            //point+1:是从下标point之后开始赋值的
            d[i]=a[point+1+i];
        }

        int ci=0;
        int di=0;
        //合并算法
        for(int i=0;i<length+1;i++){
            //ci到底的话判断
            if(ci==length_c){
                if(di <length_d){
                    a[begin+i]=d[di];
                    di++;
                    continue;
                }
            }
            //di到底的话判断
            if(di==length_d){
                if(ci <length_c){
                    a[begin+i]=c[ci];
                    ci++;
                    continue;
                }
            }
            if(c[ci]<=d[di]){
                a[begin+i]=c[ci];
                ci++;
            }
            else{
                a[begin+i]=d[di];
                di++;
            }
        }
        return a;
    }
    //打印
    public static void printIntArray(int a[]){
            for(int i=0;i<a.length;i++){
                System.out.print(a[i]+"--");
            }
    }
}
